# Definition for a binary tree node.
from typing import Optional, List

from BuildTree import build_tree_from_level_order, TreeNode


class Solution:
    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        self.stack = []
        self.prev = None
        self.count = 1

        def inOrder(node: TreeNode):
            if not node: return
            inOrder(node.left)

            if not self.stack:
                self.stack.append([node.val, 1])
            else:
                if node.val == self.prev:
                    self.count += 1
                else:
                    self.count = 1

                while self.stack and self.count > self.stack[-1][1]:
                    self.stack.pop()
                if not self.stack or self.count >= self.stack[-1][1]:
                    self.stack.append([node.val, self.count])
            self.prev = node.val  # 上一个节点
            inOrder(node.right)

        inOrder(root)
        return [c[0] for c in self.stack]


if __name__ == '__main__':
    root = build_tree_from_level_order([1, 0, 1, 0, 0, 1, 1, 0])
    s = Solution()
    r = s.findMode(root)
    print(r)
